// 138.随机链表的复制
package Leetcode_Second_Brush;

import java.util.HashMap;
import java.util.Map;

public class Solution138 {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    Map<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {

        // 如果当前节点为 null,则拷贝的节点也为null
        if (head == null)
            return null;

        // 如果当前节点已经被拷贝过，则直接返回
        if (map.containsKey(head))
            return map.get(head);

        // 拷贝当前节点并加入map中
        Node copy = new Node(head.val);
        map.put(head, copy);

        // 为拷贝节点的 next 和 random 指针进行复制，它们指向的也是拷贝的节点
        map.get(head).next = copyRandomList(head.next);
        map.get(head).random = copyRandomList(head.random);

        // 返回当前节点的拷贝
        return map.get(head);
    }
}
